/*
    2. Write a program in C to create a singly linked list of n nodes and display it in reverse order. Go to the editor
    Test Data :
    Input the number of nodes : 3
    Input data for node 1 : 5
    Input data for node 2 : 6
    Input data for node 3 : 7
    Expected Output :

    Data entered in the list are :                                                                               
    Data = 5                                                                                                     
    Data = 6                                                                                                     
    Data = 7                                                                                                     
                                                                                                                
    The list in reverse are :                                                                                    
    Data = 7                                                                                                     
    Data = 6                                                                                                     
    Data = 5 
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct node* List;
typedef struct node{
    int x;
    List next;
} Node;

List createList(int n)
{
    int i;
    List root = NULL;
    List newNode = NULL;
    List curNode = NULL;

    for(i = 0; i < n; i++){
        newNode = (List)malloc(sizeof(Node));
        if(newNode == NULL) 
            return NULL;
        printf("Input data for node %d : ", i);
        scanf("%d", &(newNode->x));
        newNode->next = NULL;
        if(root == NULL){
            root = newNode;
            curNode = newNode;
        }else{
            curNode->next = newNode;
            curNode = newNode;
        }        
    }

    return root;
}

int getLengthList(List root)
{
    List tl = root;
    int len = 0;
    for(;tl != NULL; tl = tl->next){
        len++;
    }
    return len;
}

List printReveseList(List root)
{
    List curNode = root;
    List lastNode = NULL;
    List *stackroot = NULL;
    List *stack;
    int length = getLengthList(root);
    int i;
    stackroot = (List *)malloc(length * sizeof(List));
    stack = stackroot;
    for(curNode = root; curNode != NULL; curNode = curNode->next, stack++){
        *stack = curNode;    
    }

    printf("\nThe list in reverse are : \n");
    for(i = length; i > 0; i--){
        printf("Data = %d\n", (*(stackroot + i - 1))->x);
    }
}

List reverseList(List root)
{
    List rootNode = NULL;
    List curNode = NULL; 
    List nextNode = NULL;  
    List preNode = NULL; 
    List tmpNode = NULL;
    if(root == NULL) 
        return NULL;
    rootNode = root;
    preNode = root;
    curNode = root;
    nextNode = root->next;

    for(; nextNode != NULL; preNode = curNode, curNode = nextNode, nextNode = tmpNode){
        tmpNode = nextNode->next;
        nextNode->next = curNode;
    }    
    rootNode->next = NULL;
    curNode->next = preNode;

    return curNode;
}

void printList(List list)
{
    if(list == NULL){
        printf("List is empty!\n");
        return;
    }
    printf("Data entered in the list are : \n");
    for(; list != NULL; list = list->next){
        printf("Data = %d\n", list->x);
    }
}

int main(void)
{
    List root = NULL;
    List revroot = NULL;
    int n;
    printf("Input the number of nodes : ");
    scanf("%d", &n);
    root = createList(n);
    printList(root);
    revroot = reverseList(root);
    printList(revroot);
    //printReveseList(root);
    return 0;
}
